ALGORITHMES GLOUTONS

Afin de travailler sur la notion d'algorithme glouton, nous allons partir d'un cas d'étude : le monnayeur.

Exemple: le rendu de monnaie, le monnayeur

Problème

On dispose des pièces de monnaie correspondant aux valeurs ${a_0, \ldots, a_{n-1}}$ , avec $1=a_0 < a_2 \ldots < a_{n-1}$ . Pour chaque valeur le nombre de pièces est non borné.

Étant donnée une quantité $c$ entière, on veut trouver une façcon de "rendre" la somme $c$ avec un \textcolor{red}{nombre de pièces minimum}.

Une instance du problème est la donnée des valeurs faciales des pièces ${a_0, \ldots, a_{n-1}}$ , avec $1=a_0 < a_2 \ldots < a_{n-1}$ et de la somme $c$ à payer.

Une solution est pour chaque type de pièce ( $0 \le i \le n-1$ ) un nombre de pièces $n b_{i}$ telle que $\sum_{i=0}^{n-1} nb_i* a_i =c$ : on a bien payé $c$ (exactement).

Elle est optimale si $\sum_{i=0}^{n-1} nb_i$ est minimal : on a minimisé la fonction objectif, ici le nombre total de pièces.

Une instance

Les pièces : $a_{0} = 1, a_{1} = 2, a_{2} = 5, a_{3} = 10, a_{4} = 20$
La somme à payer $c = 26$ .

Solution

1 pièce de 20, pas de pièce de 10, 1 pièce de 5, pas de pièce de 2, 1 pièce de 1.
soit au total 3 pièces.

Cette solution est-elle optimale ? Peut-on faire mieux ? Pourquoi ? Comment justifier que la solution est optimale ?

Preuve par cas?

Si on utilise 1 pièce de 20, il reste $6$ à payer: au moins deux pièces !
Si on utilise 0 pièce de 20, il reste $26$ à payer en 10, 5, 2, 1: au moins 3 pièces.

Donc c'est optimal !

L'algorithme

En pseudo code

// somme à payer entière >0 
// valeurs des pièces: $1=a[0] < ...< a[n-1]$
// les a[i] sont les valeurs de pièces triés en croissant 
int nb_pieces=0; //solution vide  
int[n] nb;  //initialisé à 0 
for (int i=n−1;i >= 0;i--) do
    nb[i] = somme/a[i] ;
    nb_pieces = nb_pieces + nb[i];
    somme = somme modulo a[i];
end

En python

# somme à payer entière >0 
# La liste ListeMontants est triée par montant croissant
def money(somme,ListeMontants) :
    ListeNbPieces=[0 for x in ListeMontants]
    for k in range(len(ListeMontants),0,-1) :
        ListeNbPieces[k]=somme//ListeMontants[k]
        somme=somme%ListeMontants[k]
    return somme,ListeNbPieces

L'algorithme est-il correct?

Exemple 1

Par exemple, soit 26 à payer en pièces de 7, 6, 1. L'algorithme glouton répond 3 Pièces de 7, 5 pièces de 1

La solution optimale est 2 pièces de 7, 2 pièces de 6

Donc, Non, l'algo n'est pas correct!

Exemple 2

Encore un plus petit exemple : soit le système de pièces (1, 3, 4), la somme de 6 à payer.

Le glouton rendra 4 puis 1 puis 1 donc 3 pièces alors qu'on peut rendre 3 et 3 soit 2 pièces,

Exemple 3

Soit un ancien système britannique: 1, 2, 6, 12, 24, 30, 60, 240

Soit la somme à payer de 48.

L'algorithme glouton était-il optimal?

A vous de jouer !

Pour rendre 48, l'algorithme glouton n'est pas optimal.

Système canonique

On appelle canonique un système de pièces pour lequel l'algorithme glouton est optimal. Les systèmes actuels le sont (presque?) tous.

p := [0, 0, ..., 0]
pour chaque i de 1 à  n:
    tant que v[i] <= S:
        p[i] := p[i] + 1
        S := S - v[i]

Quand est-il correct?

Par exemple, est-il toujours correct pour $1, 2, 5, 10, 20$ ?

La solution produite par l'algorithme glouton est

$g_{20}=c \div 20$
$g_{10}=(c \mod 20) \div 10$
$g_5= ((c \mod 20) \mod 10 )\div 5$ soit $g_5= (c \mod 10 )\div 5$
$g_2= ((c \mod 10 ) \mod 5 )\div 2$ soit $g_2= (c \mod 5 )\div 2$
$g1=(c \mod 5) \mod 2$

Que dire de l'optimale?

Soit $o_{20},o_{10},o_5,o_2,o_1$ une solution optimale. On a $c=20*o_{20}+10*o_{10}+5*o_{5}+2*o_{2}+o_1$

Alors, $o_{1} < 2$ , sinon on peut remplacer $2$ pièces de $1$ par une de $2$ .

De même, $o_{2} < 3$ , sinon, on remplace 3 pièces de $2$ par une de $5$ et une de $1$ .

De plus si $o_{2} = 2$ , alors $o_{1} = 0$ , sinon on remplace deux de $2$ et une de $1$ par une de $5$ ;

$o_{5} < 2$ , sinon, on remplace deux de $5$ par une de $10$ .

$o_{10}<2$ , sinon, on remplace deux de $10$ par une de $20$ .

Que dire de l'optimale?

$10*o_{10}+5*o_{5}+2*o_{2}+o_{1}<=10+5+4<20$

$c=20*o_{20}+10*o_{10}+5*o_{5}+2*o_{2}+o_1$ .

Donc $o_{20}= c \div \ 20= g_{20}$ et $10*o_{10}+5*o_{5}+2*o_{2}+o_1=c \ mod \ 20$ .

De même, $5*o_5+2*o_{2}+o_1<10$ donc $o_{10}= c \ mod \ 20 \div \ 10= g_{10}$ .

Donc $5*o_5+2*o_{2}+o_1=c\ mod \ 10$ ;

Comme $2*o_{2}+o_1<5$ , $o_5=c \ mod 10 \div 5= g_5$ et $2*o_{2}+o_1=c \ mod \ 5$

De même, $o_2=(c\ mod \ 5 )\div \ 2 =g_2, o_1= c \ mod \ 5 \ mod 2 = g_1$ .

Le glouton est-il optimal?

Pour ce système $1, 2, 5, 10, 20$ , la solution gloutonne est (l'unique) optimale.

Pour le système $1, 2, 5, 10, 20, 50$ , la solution gloutonne est-elle optimale?

Principe général d'un algorithme glouton

Généralités

Les algorithmes dits gloutons (en anglais greedy algorithm) servent à résoudre certains problèmes d'optimisation.

Un problème d'optimisation : on cherche à construire une solution à un problème qui optimise une fonction objectif. Un problème d'optimisation se définit comme :

un ensemble fini d’éléments, $E$ ,
une solution au problème est construite à partir des éléments de $E$ : c’est par exemple une partie de $E$ ou un multi-ensemble d’éléments de $E$ ou une suite (finie) d’éléments de $E$ ou une permutation de $E$ qui satisfait une certaine contrainte.
à chaque solution $S$ est associée une fonction objectif $v (S)$ : on cherche donc une solution qui maximise (ou minimise) cette fonction objectif.

On peut utiliser un algorithme d’approximation pour résoudre le problème d'optimisation : il fournit toujours une solution mais pas forcément une solution optimale. Bien sûr, on souhaite qu’il soit efficace.

Un algorithme d’approximation peut être:

déterministe - pour une entrée donnée, il donnera toujours la même solution (heuristiques gloutonnes, optimum local, tabou...)
non déterministe : recuit simulé, algorithme génétique...

Le principe d’une méthode gloutonne :

Avaler tout ce qu’on peut = Construire au fur et à mesure une solution en faisant les choix qui paraissent optimaux localement

On procède de façon séquentielle, en faisant à chaque étape le choix qui semble localement le meilleur.

On ne revient jamais en arrière.
Il s'agit d'une progression descendante, à chaque étape on fait un choix puis on résoud un problème plus petit issu de ce choix.

Dans certains cas, cela donnera finalement la meilleure solution : on parlera d’algorithmes gloutons exacts.

Dans d’autres, non, on parlera d’heuristiques gloutonnes.

En général, le fait que le résultat soit correct est facile, le fait qu'il soit optimal n'est pas évident.

Le schéma de la méthode gloutonne

Il est basé sur un critère local de sélection des éléments de $E$ pour construire une solution optimale. En fait, on travaille sur l’objet "solution partielle" - "début de solution"- et on doit disposer de :

select : qui choisit le meilleur élément restant selon le critère glouton.
complete? qui teste si une solution partielle est une solution (complète).
ajoutPossible? qui teste si un élément peut être ajouté à une solution partielle, i.e. si la solution partielle reste un début de solution possible après l’ajout de l’élément. Dans certains cas, c’est toujours vrai !
ajout qui permet d’ajouter un élément à une solution si c’est possible.

Schémas d’algo glouton

// on initialise l’ensemble des "briques"
// élémentaires des solutions.
Ens.init() ;
// on initialise la solution :
// ensemble (ou suite) "vide" ou..
Sol.Init() ;
while (Non Sol.complete ?() et Ens.NonVide ?()) do
    //on choisit x selon critère glouton
    x ← Ens.select();
    if Sol.ajoutPossible(x) then
        Sol.ajout(x) ; fsi ;
    //dans certains problèmes, toujours le cas
    if CertainesConditions then
        Ens.retirer(x) ;
    // selon les cas, x considéré une fois ou plus
end
// la Solution partielle est a priori complète
return Sol ;

Autre schéma :

Algorithme vorace
Début
S <- EnsembleVide
C <- ensemble des candidats à la solution
Tant que S n’est pas une solution et C <> EnsembleVide Faire
    x <- choisir un élément de C le plus prometteur
    C <- C - x
    Si realisable(solution,x) Alors
        solution <- union(solution, x)
    Finsi
FinTantQue
Si S est une solution Alors
    Retourner S
Sinon
    Retourner pas de solution
FinSi

Pour sélectionner, on trie souvent tout simplement la liste des éléments selon le critère glouton au départ ; on balaye ensuite cette liste dans l’ordre.

Ceci est un schéma général qui a l’avantage et les inconvénients d’un schéma : dans certains cas, c’est encore plus simple ! par exemple, lorsque la solution recherchée est une permutation, en général l’algorithme se réduit au tri selon le critère glouton ! dans d’autres cas, les “solutions” sont un peu plus compliquées et on a besoin d’un schéma un peu plus sophistiqué.